[[분류:수학]][[분류:정보]] ==개요== 이 문서는 '쉽게 배우는 알고리즘'이라는 책에 기반하여 작성되었다. 시간 복잡도(time complexity)는 알고리즘이 문제를 해결하는 데 걸리는 시간이 입력의 크기에 따라 어떻게 증가하는지를 나타내는 함수적 관계를 의미한다. 이는 실제 실행 시간을 직접 측정하는 것이 아니라, 입력 크기 n에 대해 알고리즘이 수행하는 연산량의 증가 양상을 수학적으로 분석하는 개념이다. 알고리즘의 시간 복잡도는 일반적으로 입력을 나타내는 문자열의 길이나 데이터의 크기를 변수로 하는 함수를 보통 T(n)으로 표현한다. [[수학]]에서 n은 실수이지만 [[정보]]에서는 일반적으로 n이 무한으로 가는 상황을 가정한다. 앞으로 나올 시간복잡도 정의도 절댓값을 쓰지 않고 표현할 것이다. ==정의== [[정보(교과목)|정보]] 시간에는 Big-O 표기법을 배울 때는 그냥 계수를 날려버리고, 낮은 차수는 무시하라고 배운다. 예를 들어서 알고리즘 계산 시간 상한이 [math(3n^2+5n+4)]라면 [math(O(n^2))]와 같이 쓰는 것. 하지만 엄밀하게 들어가면 상당히 복잡하다. 시간 복잡도 분석에는 빅 오 표기법 말고도 대표적으로 5가지의 종류가 있다. ===Big-O=== 알고리즘의 점근적 '''상한'''을 나타낸다. 따라서 [math(n^2=O(n^2))]일 뿐만 아니라 [math(n=O(n^2))], [math(1=O(n^2))]이다. 정확한 정의는 다음과 같다. [math(f(n)=O(g(n)){\iff}\exists\;c>0,\exists\;n_{0}>0\;s.t.\;\forall\;n\geq n_{0}, f(n) \leq cg(n))] 즉, 이는 충분히 큰 입력 크기에 대해 함수 [math(f(n))]이 [math(g(n))]의 상수배보다 빠르게 증가하지 않음을 의미한다. 함수의 정확한 성장률이 아니라, 상한에 대한 점근적 분류를 제공한다. ===Big-Omega=== 알고리즘의 점근적 '''하한'''을 나타낸다. 마찬가지로 [math(n^2=Ω(n^2))]일 뿐만 아니라 [math(n^3=Ω(n^2))], [math(2^n=Ω(n^2))]이다. 정확한 정의는 다음과 같다. [math(f(n)=Ω(g(n)){\iff}\exists\;c>0,\exists\;n_{0}>0\;s.t.\;\forall\;n\geq n_{0}, cg(n) \leq f(n))] 마찬가지로 [math(f(n))]이 [math(g(n))]의 상수배보다 같거나 빠르게 증가함을 의미한다. ===Big-Theta=== [math(f(n))]과 [math(g(n))]의 증가율이 거의 같음을 나타내는 매우 타이트한 표현이다. 많은 학생들이 Big-O의 정의를 Big-Theta와 헷갈려 한다. Big-Theta는 Big-O와 Big-Omega의 교집합과 같으며 정확한 정의는 다음과 같다. [math(f(n)=Θ(g(n)){\iff}\exists\;c_{1},c_{2}>0,\exists\;n_{0}>0\;s.t.\;\forall\;n\geq n_{0}, c_{1}g(n) \leq f(n) \leq c_{2}g(n))] ===Little-o=== Little-o는 상한을 나타내지만 Big-O와 다르게, '''엄밀하게''' 작아야 한다. 즉 Big-O에서 등호가 하나 빠진 거라고 볼 수 있다. 정의는 다음과 같다. [math(f(n)=o(g(n)){\iff}\exists\;c>0,\exists\;n_{0}>0\;s.t.\;\forall\;n\geq n_{0}, f(n) < cg(n))] 간단히 말하면 [math(\lim\limits_{n\to\infty} \dfrac{f(n)}{g(n)}=0)]이다. g(n)이 f(n)을 완전 찍어누른다는 것. ===Little-omega=== Little-omega도 마찬가지로 Big-Omega에서 등호가 하나 빠진 거라고 볼 수 있다. 정의는 다음과 같다. [math(f(n)=ω(g(n)){\iff}\exists\;c>0,\exists\;n_{0}>0\;s.t.\;\forall\;n\geq n_{0}, cg(n) < f(n))] 간단히 말하면 [math(\lim\limits_{n\to\infty} \dfrac{f(n)}{g(n)}=\infty)]이다. ==분석== 수행 시간이라는 것은 몇 분, 몇 초라는 절대적 시간이 아니라 연산의 양 또는 횟수를 의미한다. 이는 컴퓨터의 성능이나 데이터의 상태와 무관한 객관적인 기준을 마련하기 위함이다. 실무에서는 입력 크기 n이 무한대로 커지는 상황을 가정하며, 최악의 경우를 우선 고려한다. 주로 재귀 알고리즘은 자기 자신을 호출하는 특성 때문에 점화식으로 복잡도를 표현할 수 있다. 점화식은 [[수학]]에서 점화식 풀 때랑 똑같다고 생각하면 된다. 좌변에는 T(n), 우변에는 T로 표현되는 함수와 f(n)의 합으로 구성된다.[* T(n)은 여기서 수행시간이다.] 이 때 f(n)은 [math(O(n^2))]이든 [math(Ω(nlogn))]이든 뭐든 상관 없이, 점근 표기법을 함수처럼 쓸 수 있다.[* 정보에서 쓰는 관용적 표현이다. 수학에서는 엄밀하게 써야 한다.] 여기서 점화식을 통한 점근적 분석 방법을 총 3가지로 소개하겠다. ===반복 대치=== 점화식을 더 작은 문제의 식으로 계속해서 풀어서 전개하는 방식이다. 예를 들어 [math(T(n)=T(n−1)+c)]일 때[* 재귀적으로 구하는 팩토리얼 함수가 이와 같다. c는 상수시간으로, T(1) 초과의 잉여시간이라고 보면 된다.] 직접 [math(n-1, n-2, n-3,...)]을 대입해보자. 그럼 [math(T(n)=T(n−k)+kc)]가 된다. [math(n-k=1)]이 되는 지점에서 [math(T(n)=T(1)+(n-1)c)]이 되고, 즉 [math(T(n) \leq cn)]이므로 [math(T(n)=O(n))]임을 알 수 있다. ===추정 후 증명=== 놀랍게도 수학적 귀납법을 사용한다. 점화식의 모양을 보고 점근적 복잡도를 먼저 '''추정'''한 뒤 수학적 귀납법을 통해 그것이 옳음을 증명하는 방법이다. --개인적으로 3가지 중에 가장 어렵다-- 1. 경계조건(n=1,2,...)에서 성립함을 보인다. 2. n보다 작은 모든 값에 대해 성립한다고 가정하고, 이를 바탕으로 n에서도 성립함을 유도한다. 예를 들어 [math(T(n)=2T(n/2)+n)]일 때[* 정렬 알고리즘 중 병합 정렬이 이와 같다], [math(T(n)=O(nlogn))]임을 가정하자. [math(T(n/2)≤c(n/2)log(n/2))]라고 가정하고 대입하면, [math(T(n)≤2(c(n/2)log(n/2))+n=cn(logn−log2)+n=cnlogn−cn+n)]이 된다. 여기서 [math(c≥1)]이면 [math(T(n)≤cnlogn)]이 성립하여 증명된다. ===마스터 정리=== 특정한 형태의 점화식 [math(T(n)=aT(n/b)+f(n))]에 대해 복잡도를 즉시 결정할 수 있는 공식이다. 이 정리는 문제를 쪼개고 해결하는 비용인 [math(h(n) = n^{\log_b a})]와 오버헤드 비용 [math(f(n))]의 크기를 비교하여 다음과 같이 3가지 케이스로 나눈다. '''Case 1.''' [math(h(n))]이 지배적인 경우: [math(f(n) = O(n^{\log_b a - \epsilon}))]인 양의 상수 [math(\epsilon)]이 존재할 때: [math(T(n) = \Theta(n^{\log_b a}))] '''Case 2.''' [math(h(n))]과 [math(f(n))]의 점근적으로 같을 때: [math(f(n) = \Theta(n^{\log_b a}))]일 때: [math(T(n) = \Theta(n^{\log_b a} \log n))] [* 둘다 같으면 보너스로 [math(log n)]이 들어온다고 생각하자.] '''Case 3.''' [math(f(n))]이 지배적인 경우: [math(f(n) = \Omega(n^{\log_b a + \epsilon}))]인 양의 상수 [math(\epsilon)]이 존재하고, [math(af(n/b) \le cf(n))]를 만족하는 상수 [math(c < 1)]과 충분히 큰 모든 [math(n)]이 존재할 때: [math(T(n) = \Theta(f(n)))] 이 정리는 해당하는 꼴만 같으면 직관적으로 분석하기 가장 쉬운 방법이다. ==관련 문서== * [[알고리즘]] * [[정렬 알고리즘]] * [[탐색 알고리즘]]
